package 左哥算法.ch19线段树;


import java.util.Random;

public class 线段树求区间最小值 {

    public static void main(String[] args) {
        long[] arr = {3, 83, 33, 9, 9, 87};
        SegmentTree segmentTree = new SegmentTree(arr);
        System.out.println(segmentTree.query(1,1,arr.length,1,4));
    }
    public static class SegmentTree {
        private int N;  // 原始数组的长度
        private long[] origin;  // 存储原始数组
        public long[] tree;  // 存储每个区间的最小值

        // 构造函数，接收一个长整型数组作为参数，用于初始化线段树
        public SegmentTree(long[] origin) {
            N = origin.length;  // 获取原始数组的长度
            this.origin = new long[N + 1];  // 初始化原始数组
            for (int i = 0; i < N; i++) {
                this.origin[i + 1] = origin[i];  // 将原始数组的值复制到新的数组中
            }
            int lenS = (int) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2) + 1));  // 计算线段树的长度
            this.tree = new long[lenS];  // 初始化线段树
            build(1, 1, N);  // 构建线段树
        }

        // 构建线段树的函数
        private void build(int i, int l, int r) {
            if (l == r) {  // 如果左右边界相等，就将原始数组的值赋给当前节点
                tree[i] = origin[l];
                return;
            }
            int mid = (l + r) >> 1;  // 计算中间值
            build(i << 1, l, mid);  // 构建左子树
            build(i << 1 | 1, mid + 1, r);  // 构建右子树
            pushUp(i);  // 更新当前节点的值
        }

        // 更新当前节点的值的函数
        private void pushUp(int i) {
            tree[i] = Math.min(tree[i << 1], tree[i << 1 | 1]);  // 将当前节点的值更新为其两个子节点的最小值
        }

        // 更新原始数组和线段树的函数
        public void update(int i, int l, int r, int x, long val) {
            if (l == r) {  // 抵达叶子节点
                tree[i] = val;
                return;
            }
            int mid = (l + r) >> 1;  // 计算中间值
            if (x <= mid)    // 如果更新的位置在左子树，就更新左子树
                update(i << 1, l, mid, x, val);
            else  // 否则更新右子树
                update(i << 1 | 1, mid + 1, r, x, val);
            pushUp(i);  // 更新当前节点的值
        }

        // 查询区间最小值的函数
        public long query(int i, int l, int r, int L, int R) {
            if (L <= l && R >= r) {    // 如果查询的区间包含了当前节点的区间，就返回当前节点的值
                return tree[i];
            }
            int mid = (l + r) >> 1;  // 计算中间值
            long min = Long.MAX_VALUE;  // 初始化最小值为最大值
            if (L <= mid)  // 如果查询的区间包含了左子树，就在左子树中查询
                min = Math.min(min,query(i << 1, l, mid, L, R));
            if (R > mid)  // 如果查询的区间包含了右子树，就在右子树中查询
                min =Math.min(min, query(i << 1 | 1, mid + 1, r, L, R));
            return min;  // 返回查询结果
        }
    }

    static class Answer{
        long[] arr;

        public Answer(long[] arr) {
            this.arr = new long[arr.length+1];
            System.arraycopy(arr,0,this.arr,1,arr.length);
        }

        public void update(int i,long val){
            this.arr[i]=val;
        }

        public long query(int L,int R){
            long min=Long.MAX_VALUE;
            while (L<=R){
                min=Math.min(min,arr[L++]);
            }
            return min;
        }

        public static void main(String[] args) {
            int count=100000;
            Random r=new Random();
            while (count-->0){
                int n = r.nextInt(10) + 1;
                long[] arr=new long[n];
                for (int i = 0; i < n; i++) {
                    arr[i]=r.nextInt(100);
                }
                SegmentTree segmentTree = new SegmentTree(arr);
                Answer answer = new Answer(arr);
                for (int i = 0; i < n; i++) {
                    int L=r.nextInt(n)+1;
                    int R=L+r.nextInt(n-L+1);
                    if (r.nextBoolean()){
                        int x=r.nextInt(n)+1;
                        int val = r.nextInt(100);
                        segmentTree.update(1,1,n,x,val);
                        answer.update(x,val);
                    }else {
                        long ans1 = segmentTree.query(1, 1, n, L, R);
                        long ans2 = answer.query(L, R);
                        if (ans1!=ans2){
                            System.out.println("error");
                        }
                    }
                }
            }
        }
    }
}
